1. Field of the Invention
The present invention relates to a cache memory for a texture mapping process which is applicable to a high performance three-dimensional graphics card for a personal computer, three-dimensional game machines and other fields requiring small and high performance three-dimensional graphics. More particularly, the present invention relates to a cache memory capable of accelerating a texture mapping process based upon a hardware-used mipmapping process using a trilinear interpolation, and a method enabling a reduction in penalty due to a cache miss by, with hardware-based prediction, prefetching textures to be needed in the future.
2. Description of the Prior Art
For a three-dimensional graphics system, a texture mapping technique is mainly used to obtain more realistic scenes. Texture mapping is a technique that applies a two-dimensional image acquired by a camera, onto an object's surface in order to have a textured surface of a three-dimensional object, wherein the texture refers to a two-dimensional source image and each point element in the texture is called a texel to be associated with each pixel of the displayed portion.
Rather than, after applying the two-dimensional image, or texture, on a surface of the three-dimensional object, projecting the result to a two-dimensional display screen, a method permitting a reduction in computational amount in applying the above-mentioned texture mapping technique is used which includes obtaining coordinates of the object's surface in the three-dimensional space from each pixel of the image projected to the two-dimensional screen, computing two-dimensional texture coordinates corresponding thereto to obtain associated texels, and defining colors of the pixels to be represented on the display screen.
However, such a texture mapping technique causes an aliasing phenomenon, because an area in the texture space, mapped to one pixel represented on the display screen, is not exactly mapped to an area of one texel.
The concept of the mipmapping technique will be explained with reference to FIG. 1 representing an example. On the right side of FIG. 1, there is shown a road projected to the two-dimensional display screen. Assuming that pixels located near the observer and associated with an area ‘a’ or ‘b’ of the projected road are to be mapped into one texel in the texture space, other pixels located far from the observer and associated with, such as, an area ‘c’ or ‘d’ would be mapped into the texels in the texture space. Therefore, one texture, capable of being representative of the texels, needs to be taken to be mapped into one pixel on the display screen. Otherwise, a distorted image results.
As an easy method of obtaining one representative texel, a method is frequently used in which the representative texel is obtained by taking an average of the values of all texels in the area mapped into the texture space, which method is called a texture filtering.
However, since the above-described texture filtering is a time consuming process, the mipmapping technique is frequently used as a less time consuming process.
In the mipmapping process, as shown on the left side of FIG. 1, the original or base texture image (which is an image indicated by LOD 0 in FIG. 1, wherein the LOD (Level Of Detail) denotes a value representing the number of texels to which one pixel on the display screen corresponds) is pre-filtered and subsampled to prepare textures or mipmaps of various LOD levels. Based upon the LOD and (u, v) coordinates which are computed at the time when the pixel to be displayed on the screen is mapped into the texture space, the texels required are taken from appropriate LOD levels on the mipmap and then displayed on the screen.
While the computed LOD value and (u, v) coordinates which are mapped onto the texture space appear as mixed numbers, respectively, i.e., (x, y) coordinates on the screen in integer representation are coordinate-transformed by using a transform matrix to give the mixed numbers, the values presently existing on the mipmap are associated with the locations of the integer value of the LOD and the (u, v) coordinates in integer representation. Accordingly, there is no texel value at the location of the precise LOD and (u, v) coordinates in the texture space into which the pixel to be rendered on the display screen is mapped. However, the integer values nearest those non-integer texel values are read from the mipmap, and then the distance difference between the read values and the values at the accurate locations are used for the interpolation.
Referring to FIG. 2, the following is to explain an example on how to obtain the texel value with respect to a pixel mapped with the LOD=0.6 and (u, v)=(23.25, 30.50).
(i) Since the value of the LOD is 0.6, the (23, 30), (23, 31), (24, 30) and (24, 31) coordinates are selected from integers that are nearest to the values of u=23.25 and v=30.50, at the level of LOD 0, from which the texel values are read to obtain the representative value at the level of LOD 0, based on the distance between the actual exact coordinates and those coordinates.
(ii) To obtain the representative value at the level of LOD 1, the (11, 15), (11, 16), (12, 15) and (12, 16) coordinates are selected from integers that are nearest to the values of u=23.25/2=11.62 and v=30.50/2=15.25, from which the telex values are read to obtain the representative value at the level of LOD 1, based on the distance between the actual exact coordinates and those coordinates.
(iii) The difference between the two representative values thus obtained and the actual exact value, 0.6 of LOD, is used to obtain the final representative texel value, as shown in FIG. 2.
The mipmapping technique previously prepares the textures with various levels of the LOD for high-speed texture mapping, reads eight texels to obtain a representative texel value to be used in executing the program, and performs the interpolation (such an interpolation method is called a trilinear interpolation) and uses the interpolated resulting value as a representative value.
While the above-mentioned mipmapping technique provides more rapid processing, a problem still remains in that a large amount of time is required to sequentially read eight texels from the memory which is needed to perform the three-dimensional graphics mipmapping process.
Therefore, in order to solve such a problem, there has been proposed a structure as shown in FIG. 3, which enables a representative texel value to be obtained, by providing separate memory banks capable of storing texels of two levels of LOD, accessing simultaneously eight texels using the memory banks where the texels are stored with the mapping relation between the texels stored in each of the memory banks and the position of the texels in the texture space, as shown in FIG. 4 (where a number in each texel area denotes a memory bank number to which the texel is to be stored) and sending the accessed eight texels to the trilinear interpolator to perform the interpolation in one clock cycle, and obtaining a representative texel value.
However, since various sizes of texture images are used in applications of the actual three-dimensional graphics system, the use of texram as shown in FIG. 3 leads to the need of a memory of more capacity than that of a texture image to be used in the future. In a case where the value of the LOD greatly varies every time each pixel is rendered, the time is considerably consumed in a continuous change of the contents of the memory. This results in inefficient use of the memory and an increase in cost. Thus, the structure as shown in FIG. 3 has a drawback in the practical use.
Proposed as another common concept is a clipmap, which enables a great reduction in the memory capacity of the system in a texture mapping process using a large texture image. In this scheme, since on the mipmap as shown in FIG. 5, the lower the LOD level is, the more the space for storing the texture image is increased in geometrical progression, only the textures of several upper levels of the LOD are placed in upper portions of the current system memory, and the currently rendered portions among the reaming values of the LOD levels are also placed. If necessary, other portions can be fetched and used from a hard disk where the overall mipmap has been stored.
However, the above-mentioned clipmap method is applied between the hard disk and the system memory and entirely implemented in a software manner. Therefore, the main object of this method is essentially to reduce the capacity of the system memory, but not suitable for accelerating the texture mapping.